﻿#define _CRT_SECURE_NO_WARNINGS 
#include<iostream>
#include<vector>


class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        vector<int> ret;
        unordered_map<string, int> hash1; // 保存 words ⾥⾯所有单词的频次
        for (auto& s : words)
            hash1[s]++;
        int len = words[0].size(), m = words.size();
        for (int i = 0; i < len; i++) // 执⾏ len 次
        {
            unordered_map<string, int> hash2; // 维护窗⼝内单词的频次
            for (int left = i, right = i, count = 0; right + len <= s.size();
                right += len) {
                // 进窗⼝ + 维护 count
                string in = s.substr(right, len);
                hash2[in]++;
                if (hash1.count(in) && hash2[in] <= hash1[in])
                    count++;
                // 判断
                if (right - left + 1 > len * m) {
                    // 出窗⼝ + 维护 count
                    string out = s.substr(left, len);
                    if (hash1.count(out) && hash2[out] <= hash1[out])
                        count--;
                    hash2[out]--;
                    left += len;
                }
                // 更新结果
                if (count == m)
                    ret.push_back(left);
            }
        }
        return ret;
    }
};



//////////////////////////////////////////////////////////////////
class Solution {
public:
    string minWindow(string s, string t) {
        int hash1[128] = { 0 }; // 统计字符串 t 中每⼀个字符的频次
        int kinds = 0;        // 统计有效字符有多少种
        for (auto ch : t)
            if (hash1[ch]++ == 0)
                kinds++;
        int hash2[128] = { 0 }; // 统计窗⼝内每个字符的频次
        int minlen = INT_MAX, begin = -1;
        for (int left = 0, right = 0, count = 0; right < s.size(); right++) {
            char in = s[right];
            if (++hash2[in] == hash1[in])
                count++;           // 进窗⼝ + 维护 count
            while (count == kinds) // 判断条件
            {
                if (right - left + 1 < minlen) // 更新结果
                {
                    minlen = right - left + 1;
                    begin = left;
                }
                char out = s[left++];
                if (hash2[out]-- == hash1[out])
                    count--; // 出窗⼝ + 维护 count
            }
        }
        if (begin == -1)
            return "";
        else
            return s.substr(begin, minlen);
    }
};

////////////////////////////////////////////////////////////////
